#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
struct ListNode
{
    int value;
    ListNode *next;
    ListNode(int value) : value(value), next(nullptr) {}
};
ListNode *initList(initializer_list<int> list)
{
    ListNode *head = nullptr;
    ListNode *cur = nullptr;
    for (int ln : list)
    {
        if (head == nullptr)
        {
            head = new ListNode(ln);
            cur = head;
        }
        else
        {
            cur->next = new ListNode(ln);
            cur = cur->next;
        }
    }
    return head;
}
ListNode *mergeTwoLink(ListNode *left, ListNode *right)
{
    ListNode *head = nullptr;
    ListNode *cur = nullptr;
    while (left != nullptr && right != nullptr)
    {
        if (left->value >= right->value)
        {
            if (head == nullptr)
            {
                head = new ListNode(right->value);
                cur = head;
            }
            else
            {
                cur->next = new ListNode(right->value);
                cur = cur->next;
            }
            right = right->next;
        }
        else
        {
            if (head == nullptr)
            {
                head = new ListNode(left->value);
                cur = head;
            }
            else
            {
                cur->next = new ListNode(left->value);
                cur = cur->next;
            }
            left = left->next;
        }
    }
    if (left != nullptr)
    {
        cur->next = left;
    }
    if (right != nullptr)
    {
        cur->next = right;
    }
    return head;
}
ListNode *mergeLink(vector<ListNode *> &vLink, int i, int j)
{
    if (i >= j)
    {
        return vLink[i];
    }

    int mid = (i + j) / 2;
    ListNode *left = mergeLink(vLink, i, mid);
    ListNode *right = mergeLink(vLink, mid + 1, j);
    return mergeTwoLink(left, right);
}
int main()
{
    ListNode *p1 = initList({1, 3, 5, 7});
    ListNode *p2 = initList({2, 4});
    ListNode *p3 = initList({6, 8 });
    ListNode *p4 = initList({9 });
    ListNode *p5 = initList({10 });

    vector<ListNode *> vLink;
    vLink.push_back(p1);
    vLink.push_back(p2);
    vLink.push_back(p3);
    vLink.push_back(p4);
    vLink.push_back(p5);
    ListNode *result = mergeLink(vLink, 0, vLink.size() - 1);
    for (; result != nullptr; result = result->next)
    {
        cout << result->value << " ";
    }
    cout << endl;
}